package com.bitauto.i.commonUtils.arithmetic;

public class BottleExchange {
    public static int minInitialBottles1(int target) {
        int x = 0; // 初始购买瓶数
        int i=0;
        while (true) {
            int total = x; // 总共喝到的水
            int caps = x;   // 当前瓶盖数
            while (caps >= 3) {
                int exchanged = caps / 3; // 兑换的水
                total += exchanged;
                caps = caps % 3 + exchanged; // 剩余瓶盖 + 新瓶盖
                i++;
                System.out.println("第"+i+"次迭代，目前喝了"+total+"瓶，caps="+caps);
            }
            if (total >= target) {
                return x;
            }
            x++;
            System.out.println("初始化买水"+x+"瓶");
        }
    }

    public static int minInitialBottles2(int target) {
        // 公式: x + floor((x - 1) / 2) >= target
        // 解得 x >= ceil( (2 * target + 1) / 3 )
        return (int) Math.ceil((2 * target + 1) / 3.0);
    }

    public static void main(String[] args) {
        int target = 100;
        System.out.println("至少需要购买: " + minInitialBottles1(target) + " 瓶水");
        System.out.println("至少需要购买: " + minInitialBottles2(target) + " 瓶水");
        // 输出: 至少需要购买: 67 瓶水
    }
}
